'''
https://leetcode.cn/problems/shortest-path-in-a-grid-with-obstacles-elimination/
'''
from collections import deque
from typing import List

MAX = 1 << 31


class Solution:
    def shortestPath(self, grid: List[List[int]], k: int) -> int:
        m, n = len(grid), len(grid[0])
        k = min(k, m + n - 3)
        visited = [[[False] * (k + 1) for _ in range(n)] for _ in range(m)]
        q = deque([(0, 0, k)])
        step = 0
        while q:
            for _ in range(len(q)):
                x, y, rest = q.popleft()
                if x == m - 1 and y == n - 1:
                    return step
                for tx, ty in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:
                    if tx < 0 or tx >= m or ty < 0 or ty >= n or (trest := rest - grid[tx][ty]) < 0:
                        continue
                    if not visited[tx][ty][trest]:
                        q.append((tx, ty, trest))
                        visited[tx][ty][trest] = True
            step += 1
        return -1